class Demo {
    // // 暴力枚举
    // public int reversePairs(int[] nums) {
    //     int n = nums.length;
    //     int count = 0;
    //     for (int i = 0; i < n; i++) {
    //         for (int j = i+1; j < n; j++) {
    //             if (nums[i] > 2*nums[j]) {
    //                 count++;
    //             }
    //         }
    //     }
    //     return count;
    // }

    int[] temp; // 申请辅助数组
    public int reversePairs(int[] nums) {
        int n = nums.length;
        temp = new int[n];
        return merge(nums, 0, n-1);
    }

    private int merge(int[] nums, int start, int end) {
        // 处理不符合要求的
        if (start >= end) {
            return 0;
        }
        // 处理左边、右边
        int ret = 0;
        int mid = (start+end) / 2;
        ret += merge(nums, start, mid);
        ret += merge(nums, mid+1, end);
        // 处理一左一右的情况
        int left = start, right = mid+1, i = 0;
        while (left <= mid && right <= end) { // 只有两个区间都有值时，才去计算
            // 这里得去处理数据溢出的问题
            if ((long)(nums[left]) <= 2*(long)nums[right]) { // 不符合要求的
                right++;
            } else { // 符合要求的
                ret += end-right+1;
                left++;
            }
        }
        // 进行归并排序
        left = start;
        right = mid+1;
        while (left <= mid && right <= end) { // 采取降序排序
            if (nums[left] <= nums[right]) { // 不符合要求的
                temp[i++] = nums[right++];
            } else {
                temp[i++] = nums[left++];
            }
        }

        while (left <= mid) {
            temp[i++] = nums[left++];
        }

        while (right <= end) {
            temp[i++] = nums[right++];
        }
        // 处理最后的排序问题
        for (int j = start; j <= end; j++) {
            nums[j] = temp[j-start];
        }
        return ret;
    }
}


